class Solution(object):
    def movingCount(self, threshold, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        if rows == 0 or cols == 0:
            return 0
        
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if i % 10 + i // 10 + j % 10 + j // 10 > threshold:
                    matrix[i][j] = 1
        def bfs(i,j,rows,cols,matrix):
            if matrix[i][j] == 0:
                matrix[i][j] = 2
                if i+1 < rows and j+1 >= cols:
                    bfs(i+1,j,rows,cols,matrix)
                elif i+1 >= rows and j+1 < cols:
                    bfs(i,j+1,rows,cols,matrix)
                elif i+1 < rows and j+1 < cols:
                    bfs(i+1,j,rows,cols,matrix)
                    bfs(i,j+1,rows,cols,matrix)
            
        bfs(0,0,rows,cols,matrix)
        
        cnt = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 2:
                    cnt += 1
        
        return cnt
        